public class Wu_4_2 {
    public static void main(String[] args) {
        System.out.println("#######################stack########################");
        Stack s=new Stack(10);
        for(int i=0;i<10;i++) {
            try {
                s.push(i+1);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        for(int i=0;i<10;i++){
            try {
                System.out.println(s.pop());
            }catch (Exception e){
                throw new RuntimeException(e);
            }
        }
        // the p is the start location of queue
        System.out.println("#######################queue########################");
        Queue q=new Queue(10,2);
        for(int i=0;i<9;i++) {
            try {
                q.enqueue(i+1);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        for(int i=0;i<9;i++){
            try {
                System.out.println(q.dequeue());
            }catch (Exception e){
                throw new RuntimeException(e);
            }
        }
        System.out.println("########################queueBystack#########################");
        QueuebyStack qs=new QueuebyStack(10);
        for(int i=0;i<10;i++) {
            try {
                qs.enqueue(i+1);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        for(int i=0;i<10;i++){
            try {
                System.out.println(qs.dequeue());
            }catch (Exception e){
                throw new RuntimeException(e);
            }
        }

    }
}
class QueuebyStack{
    Stack inbox;
    Stack outbox;
    public QueuebyStack(int size){
        inbox=new Stack(size);
        outbox=new Stack(size);
    }
    void enqueue(int n) throws Exception{
        if(inbox.isfull()){
            throw new Exception("Overflow");
        }else
            inbox.push(n);
    }
    int dequeue() throws Exception{
        if(outbox.isempty()){
            if(inbox.isempty()){
                throw new Exception("underflow");
            }else{
                for(int i= inbox.getTop();i>-1;i--){
                    outbox.push(inbox.pop());
                }
                return outbox.pop();
            }
        }else
            return outbox.pop();
    }
}
// circle queue has a null location
class Queue{
    private int [] array;
    private int head;
    private int tail;
    public Queue(int size,int p){
        array=new int[size+1];
        head=p-1;tail=p-1;
    }
    void enqueue(int n) throws Exception{
        if(tail-head==array.length || head==tail+1){
            throw new Exception("Overflow!");
        }else{
            if(tail==array.length-1){
                array[tail]=n;
                tail=0;
            }else{
                array[tail++]=n;
            }
        }
    }

    int dequeue() throws Exception{
        if(head==tail) {
            throw new Exception("underflow!");
        } else{
            if(head==array.length)
                head=0;
            return array[head++];
        }
    }
}
class Stack{
    private int[] array;
    private int top;
    public Stack(int size){
        array=new int[size];
        top=-1;
    }
    void push(int n) throws Exception{
        if(top>=array.length-1)
            throw new Exception("overflow!");
        else
            array[++top]=n;
    }
    int pop() throws Exception{
        if(top==-1)
            throw new Exception("underflow!");
        else
          return array[top--];
    }
    boolean isfull(){
        return top == array.length - 1;
    }
    boolean isempty(){
        return top==-1;
    }

    public int getTop() {
        return top;
    }

}
